In wireless communication systems, such as cellular, wide local area networks (WLAN), wide metropolitan area networks (WMAN), personal area networks (PANs), etc, demand for higher data rate services is growing. In such systems, typically a wireless device communicates with a network nodes such as a base station (cellular networks) or access point (APs), although wireless device to wireless device (ad hoc) communications is growing in prevalence.
To accommodate higher and higher data rates, improved receiver performance is desired. One technique for improved receiver performance is a generalized Rake structure. Generalized Rake structures typically have multiple Rake fingers collecting energy from received communications and combining them, such as by using maximal ratio combining (MRC). Another technique uses a normalized least mean squares (NLMS) based approach, such as by using a finite impulse response (FIR) filter. In such a technique, the FIR filter is used to process received communications and a NLMS algorithm is used to adjust the tap values.
Other approaches for implementing receivers use zero forcing (ZF) block linear equalizers and minimum mean square error (MMSE) equalizers. To accurately detect the data using these approaches requires that an infinite number of received samples be used, which is not practical.
One approach for handing an infinite number of samples is a sliding window Cholesky based Equalization. Although Cholesky based equalization is described in the Background, the following is provided to give context to the Detailed Description of the Preferred Embodiments and may contain information that is not publicly known or would constitute prior art.
For data sequence d={d0, d1, . . . }, a sequence r={r0, r1, . . . } is given per Equation 1.r=Sd+n  Equation 1n is a zero-mean Gaussian noise sequence with covariance given by the relationships E[nin*j]*=Σi,j; and S is a linear operator where
            (      Sd      )        i    =            ∑      j        ⁢                  S                  i          ,          j                    ⁢                        d          j                .            One approach to estimate d from r is a minimum mean square error equalization based approach per Equation 2.{circumflex over (d)}MMSE=(SHΣ−1S+I)−1SHΣ−1r  Equation 2
Whenever N≧K and S is full rank, an alternative estimation procedure often utilized in communications application is a zero-forcing block linear equalization based approach per Equation 3.{circumflex over (d)}ZF=(SHΣ−1S)−1SHΣ−1r  Equation 3Simpler forms of both Equation 2 and Equation 3 can be derived by ignoring noise correlation, Σ−1.
A solution to Equation 3 can be put into a unified framework by a two step procedure. First, a “matched filtering” operation is performed on the measured (“received”) data, as per Equation 4.y=SHΣ−1r  Equation 4The estimate of the original data is obtained by solving for {circumflex over (d)} in a linear K-equation system as per Equation 5.y=R{circumflex over (d)}  Equation 5R is a symmetric positive definite matrix.
Equation 5 can be solved via the Cholesky decomposition. This involves finding a lower triangular matrix G, such that R=GGH. Equation 5 can be solved by first finding a vector b such as by Equation 6.y=Gb  Equation 6Subsequently, {circumflex over (d)} is derived per Equation 7.b=GH{circumflex over (d)}  Equation 7
Accordingly, solving Equation 5 using Cholesky decomposition is performed in three steps. First, R is factored R=GGH, (Cholesky factorization). Second, forward substitution is performed per Equation 6. Third, backward substitution is performed per Equation 7.
Utilizing Cholesky decomposition to solve Equation 5 yields highly efficient implementations when R is banded. To estimate an infinite sequence d based on an infinite set of observations r, several assumptions are used. First, the problem is assumed to be causal, which means that ri cannot depend on dj for j>i. Additionally, the time-dependence is assumed to be finite.
In particular, the following assumptions are made. First, the noise covariance operator Σ is banded. This first assumption means that the covariance matrix for any finite subset of elements of n is banded and the bandwidth is upper-bounded by some Wn which can be referred to as the noise covariance bandwidth. Second, ri does not depend on any dj for j<i−Wd, where Wd is the data operator bandwidth. Neither the noise covariance bandwidth nor the data operator bandwidth have anything to do with the bandwidth of a communication channel.
These assumptions have the following implications. First, the matched filter operation can always be performed using a finite amount of resources with a finite delay. The operator R is banded with bandwidth W=Wn+Wd. Banded in this respect means that for any finite subset of natural numbers I, a matrix RI is formed by taking those elements of R, which have row and column indexes in I. The resulting RI is a banded matrix and its bandwidth is upper bounded by W.
Unlike the matched filtering operation, the banded nature of R is not sufficient to reduce the problem of solving Equation 5 from an infinite-dimensional operation to a sequence of finite-dimensional operations.
To solve Equation 5, a sliding window Cholesky based equalization can be used. For every i∈{0, 1, . . . }, the index set is Ii={i−V, i−V+1, . . . i+V−1, i+V} when i>V and Ii={0, 1, . . . i+V−1, i+V} when i≦V. For every i, the matched filter vector is yi=[yj]T, j∈Ii and the matrix Ri=RIi. {circumflex over (d)}i is obtained by per Equaiton 8.yi=Ri{circumflex over (d)}  Equation 8
The middle, (V+1)th, element of the (2V+1)-element solution is taken. Since V elements are infront and behind i, this technique is referred to as a symmetric sliding window approximation. However, the number of elements before and after i do not need to be the same, so asymmetric approaches can also be used. In the asymmetric versions, more emphasis is placed either on the past or on the future symbols.
The approximation of an infinite sequence as a window is justified as follows. The inter-dependence of the estimate on a particular symbol on received data typically decreases as distance from symbol of interest increases. As a result, received data points may be neglected outside of a certain range, with negligible degradation in performance. Accordingly, a window around the element of interest can be used, such as a window leading and lagging that element by V. Also, although this approach is applicable for infinite or extremely long sequences, it can also be used for finite or fixed length sequences.
FIG. 1 is a simplified block diagram of a sliding window Cholesky based receiver. An antenna or antenna array 10 receives a communication or multiple communications over a wireless interface. The communication(s) are sampled by a sampling device 12 to produce a received vector r or multiple received vectors, based on the implementation. A channel estimation device 16 estimates a channel response h or channel responses for the communication(s).
A compute channel correlation matrix and sliding window control device 14 receives the samples r and channel response(s) h and produces a channel correlation matrix Ri corresponding to a sliding window around an element i of interest. Also, received samples corresponding to the sliding window rwini are produced. A Cholesky decomposition device 18 factors the channel correlation matrix Ri into a Cholesky factors G and GH. A forward substitution device 20 receives a Cholesky factor and the received samples and performs forward substitution. A backward substitution device 22 receives a Cholesky factor and the output of the forward substitution device 20 and produces soft values for the sliding window. Preferably, backward substitution is only performed on the values of interest, such as the middle values, to reduce complexity.
After discarding the values around the element of interest, a soft value is produced around the value of interest. Typically, this value is a spread symbol of a spread symbol vector d. The spread symbol vector d is despread by a despreader 24 to produce soft data symbols of the received communication(s). Alternately, this value may be the soft symbols themselves of the communication(s) and the despreader 24 is not required.
To analyze the complexity, the complexity of Cholesky decomposition, forward and backward substitution are analyzed. For the analysis, one symbol is used as the elements of interest and a window of V elements prior and post that symbol form the sliding window.
For Cholesky decomposition, the complexity of the square roots involved in Cholesky decomposition is assumed to be a minor part of the overall process. As a result, for a (2V+1)×(2V+1) matrix with bandwidth W the decomposition requires roughly (2V+1)(W2+3W) flops. Flop is a floating point operation (complex if the matrices are complex). For forward substitution, roughly 2(2V+1)W flops are required. For backward substitution, since only the element of interest are processed, the complexity of this step is 2(V+1)W flops.
The total complexity associated with estimation of each data symbol for the symmetric sliding window with width V in flops is then approximately given byCOMPSW(V)=2VW2+W2+12VW+9W  Equation 9
As described above, sliding window based Cholesky Equalization results in complexity that is too high for many commercial communication systems. Accordingly, it is desirable to have a lower complexity technique.